class Node:
    def __init__(self, val):
        self.val = val
        self.neighbors = {}
        self.flag = 0


class MagicDictionary(object):

    def __init__(self):
        self.tree = Node('#')

    def buildDict(self, dictionary):
        """
        :type dictionary: List[str]
        :rtype: None
        """
        for word in dictionary:
            node = self.tree
            for w in word:
                if w not in node.neighbors:
                    new_node = Node(w)
                    node.neighbors[w] = new_node
                    node = new_node
                else:
                    node = node.neighbors[w]
            node.flag = 1

    def match(self, node, word, i, n, state):
        if i == n:
            if node.flag:
                if state == 0:
                    return False
                else:
                    return True
            else:
                return False
        if state == 0:
            if word[i] in node.neighbors:
                if self.match(node.neighbors[word[i]], word, i + 1, n, 0):
                    return True
            for c in node.neighbors:
                if c != word[i]:
                    if self.match(node.neighbors[c], word, i + 1, n, 1):
                        return True
            return False
        else:
            if word[i] in node.neighbors:
                if self.match(node.neighbors[word[i]], word, i + 1, n, 1):
                    return True
                else:
                    return False
            else:
                return False

    def search(self, searchWord):
        """
        :type searchWord: str
        :rtype: bool
        """
        node = self.tree
        n = len(searchWord)
        return self.match(node, searchWord, 0, n, 0)


